package com.dy.回溯算法.电话号码的字母组合;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> list = new ArrayList<>();
        if (digits.isEmpty()) return list;
        Map<Character, String> map = new HashMap<>();
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");

        char[] digitsChar = digits.toCharArray();
        list.add("");
        for (int i = 0; i < digitsChar.length; i++) {
            String sufStr = map.get(digitsChar[i]);
            List<String> tmpList = new ArrayList<>();
            for (String str : list) { //对于每一个结果，都要新加上当前的各个字母
                for (Character character : sufStr.toCharArray()) {
                    tmpList.add(str + character);
                }
            }
            list = tmpList;//更新返回的列表

        }

        return list;
    }
    //递归
    Map<Character, String> map = new HashMap<>();

    public List<String> letterCombinations2(String digits) {
        List<String> list = new ArrayList<>();
        if (digits.isEmpty()) return list;
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");
        return letterCombinations(digits,0);

    }
    private List<String> letterCombinations(String digits,int n){
        List<String> list = new ArrayList<>();
        if(n==digits.length()-1){
            for(Character c: map.get(digits.charAt(n)).toCharArray()){
                list.add(String.valueOf(c));
            }
            return list;
        }

        list=letterCombinations(digits,n+1);
        List<String> res = new ArrayList<>();
        for(Character c: map.get(digits.charAt(n)).toCharArray()){
            for(String string:list){
                res.add(c+string);
            }
        }
        return res;

    }

    public static List<String> letterCombinations3(String digits) {
        List<String> strings = new ArrayList<>();
        if (digits.length() == 0) {
            return strings;
        }
        String[] dict = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        //选中的字母组合
        String[] arr = new String[digits.length()];
        for (int i = 0; i < digits.length(); i++) {
            arr[i] = dict[digits.charAt(i) - '0' - 2];
        }
        int startStr = 0;//循环下标
        group(arr, startStr, "",strings);
        return strings;
    }

    private static String group(String[] arr, int startStr, String str, List<String> strings) {
        char[] chars1 = arr[startStr].toCharArray();
        for (int j = 0; j < chars1.length; j++) {
            if (startStr == arr.length - 1) {
                strings.add(str + chars1[j]);
            } else {
                //startStr+1:遍历下一个字符组合;str + chars1[j]:拼接当前遍历的字符
                group(arr, startStr+1, str + chars1[j],strings);
            }
        }
        return str;
    }
}
